package ru.eas.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class ShortestPathsWithNegativeCycle {

    public static void main(String[] args) {
        String testString = "9 10 1\n" +
                "1 2 10\n" +
                "2 3 5\n" +
                "1 3 100\n" +
                "3 5 7\n" +
                "5 4 10\n" +
                "4 3 -18\n" +
                "6 1 -1\n" +
                "7 9 6\n" +
                "9 8 -15\n" +
                "8 7 3";
        Scanner scanner = new Scanner(testString);

//        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int s = scanner.nextInt();
        DirectedGraph graph = new DirectedGraph(n);
        for (int i = 0; i < m; i++) {
            graph.addEdge(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
        }
        long[] result = graph.getDistances(s);
        for (int i = 1; i < result.length; i++) {
            if (result[i] == DirectedGraph.INFINITY_DISTANCE) {
                System.out.println("*");
            } else if (result[i] == DirectedGraph.NO_SHORTEST_WAY) {
                System.out.println("-");
            } else {
                System.out.println(result[i]);
            }
        }
    }


    static class DirectedGraph {

        class Edge {
            int vertex;
            int weight;

            Edge(int vertex, int weight) {
                this.vertex = vertex;
                this.weight = weight;
            }
        }

        public static final long INFINITY_DISTANCE = Long.MAX_VALUE;
        public static final long NO_SHORTEST_WAY = Long.MIN_VALUE;

        private List<List<Edge>> vertices;
        private long[] distances;
        private int[] prev;

        public DirectedGraph(int vertexCount) {
            vertexCount++;
            vertices = new ArrayList<List<Edge>>(vertexCount);
            for (int i = 0; i < vertexCount; i++) {
                vertices.add(new ArrayList<Edge>());
            }
            distances = new long[vertexCount];
            prev = new int[vertexCount];
        }

        public void addEdge(int vertex1, int vertex2, int weight) {
            Edge edge = new Edge(vertex2, weight);
            vertices.get(vertex1).add(edge);
        }

        private void relaxAllEdges() {
            for (int v1 = 1; v1 < vertices.size(); v1++) {
                for (Edge edge : vertices.get(v1)) {
                    int v2 = edge.vertex;
                    relax(v1, v2, edge.weight);
                }
            }
        }

        private void relax(int v1, int v2, int weight) {
            if (distances[v1] == INFINITY_DISTANCE) {
                return;
            }
            long distance = distances[v1] + weight;
            if (distances[v2] > distance) {
                distances[v2] = distance;
                prev[v2] = v1;
            }
        }

        public long[] getDistances(int startVertex) {
            for (int i = 1; i < vertices.size(); i++) {
                distances[i] = INFINITY_DISTANCE;
                prev[i] = -1;
            }
            distances[startVertex] = 0;
            prev[startVertex] = startVertex;
            for (int i = 1; i < vertices.size() - 1 ; i++) {
                relaxAllEdges();
            }
            long[] result = Arrays.copyOf(distances, distances.length);

            relaxAllEdges();
            relaxAllEdges();

            for (int i = 1; i < result.length; i++) {
                if (result[i] != distances[i]) {
                    result[i] = NO_SHORTEST_WAY;
                }
            }
            return result;
        }
    }
}
